package Array.easy;

/**
 * 1. 问题描述
 *      给你一个仅由字符 '0' 和 '1' 组成的字符串 s 。一步操作中，你可以将任一 '0' 变成 '1' ，或者将 '1' 变成 '0'
 *      交替字符串 定义为：如果字符串中不存在相邻两个字符相等的情况，那么该字符串就是交替字符串。例如，字符串 "010"
 *      是交替字符串，而字符串 "0100" 不是。返回使 s 变成 交替字符串 所需的 最少 操作数。
 *
 * 2. 算法分析
 *      从题意可知所谓的交替字符为010101...或者1010101....,所以我们只需要将原字符串和这两种情况进行比较，
 *      返回最小不同的一个即可
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 生成交替二进制字符串的最少操作数 {

    /**
     * 空间复杂度比较高，因为额外开辟了两个长度为n的数组来记录可能出现的两种交替字符串的情况
     * @param s
     * @return
     */
    public int minOperations1(String s) {
        char[] charArrayS = s.toCharArray();
        int n = charArrayS.length;
        char[] temp1 = new char[n];
        char[] temp2 = new char[n];
        for(int i = 0; i < n; i++) {
            temp1[i] = (i % 2 == 0) ? '0' : '1';
            temp2[i] = (i % 2 == 0) ? '1' : '0';
        }
        int count1 = 0;
        int count2 = 0;
        for(int i = 0; i < n; i++) {
            if(temp1[i] != charArrayS[i]) {
                count1++;
            }
            if(temp2[i] != charArrayS[i]) {
                count2++;
            }
        }
        return Math.min(count1,count2);
    }

    /**
     * 优化，不需要使用额外的空间，代码逻辑同上
     * @param s
     * @return
     */
    public int minOperations2(String s) {
        int count1 = 0;  // 记录0开头的
        int count2 = 0;  // 记录1开头的
        char[] charArrayS = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            // 交替
            // 有两种交替情况0开头或者1开头
            // 实际上我们只需要想清楚第1个元素的变化即可
            // 如果s的首字符为0，说明s只可能为0开头的交替
            // 所以判断当前(这里的当前就是首)字符为1，此时count1++
            if (i % 2 == 0) {
                if (charArrayS[i] != '0') {
                    count2++;
                } else {
                    count1++;
                }
            } else {
                if (charArrayS[i] != '0') {
                    count1++;
                } else {
                    count2++;
                }
            }
        }
        return (count1 < count2) ? count1 : count2;
    }
}
